package arrays;

import java.util.HashSet;
import java.util.Set;

/**
 * 题目：
 *      给定一个不为空的整数数组，数组里面只有一个不重复的数字，要求找到这个数字
 *      y: [5 5 6 7 7]    返回6
 *
 * @Author Gavin
 * @date 2021.12.08 21:24
 */
public class array_3 {
    /**
     *解题思路1：使用set集合先把元素去重，然后把剩下的元素之和*2 减去数组里面元素的和就得到重复的那个元素了
     * 解题思路2： 使用异或运算，使数组里面的所有数进行与或运算，最后得到的值就是那个唯一的值
     *  异或运算就是两个相同的值异或的值为0，然后0和任何元素进行异或得到的是原来的值
     */

    //第一种：使用一个set集合
    //Time:O(n)   Space: O(n)
    public static int  solution(int[] arrays){
        Set<Integer> set=new HashSet<>();
        int sum=0,union=0;
        for(int pre:arrays){
            if(!set.contains(pre)){
                union+=pre;
                set.add(pre);
            }
            sum+=pre;
        }
        return 2*union-sum;
    }


    //第二种方式，节约空间复杂度
    //Time:O(n) Space:O(1)
    public static int solution2(int[] arrays){
        int num=0;
        for (int pre:arrays){
            num^=pre;
        }
        return num;
    }

    public static void main(String[] args) {
        int[] array=new int[]{1,1,2,3,3,3};
        System.out.println(solution2(array));
    }
}
